#!/usr/bin/python
# -*- coding: utf-8 -*-

'''
Introduction to Programming in Java - An Interdisciplinary Approach

All book programs ported to Python by
Scott C. King (revisionx at {gee}ma1l <dot> c0m).

All program examples pass Pylint with a perfect 10.00 score.
Pylint:  http://www.pylint.org/


Program 1.6.3 - Mixing a Markov chain

Syntax:
python transition.py < tiny.txt | python markov.py 40
tiny.txt is a required file (supplied)


Notes:
int(sys.argv[1]) == Integer.parseInt(args[0])

sys is a required import here in order to use stdin.
https://docs.python.org/2/tutorial/stdlib.html

'''

import sys


def main():
    ''' process transition matrix, compute probabilities random surfer
        lands on each page (page ranks) '''

    iterations = int(sys.argv[1])
    pages = int((sys.stdin.readline().strip().split())[0])

    # Read transition matrix
    trans_matrix = [[0 for _ in range(pages)] for _ in range(pages)]

    for row in range(pages):
        line = sys.stdin.readline().strip().split()
        for col in range(pages):
            trans_matrix[row][col] = float(line[col])

    # use the power method to compute page ranks
    rank = [0] * pages
    rank[0] = 1.0

    for _ in range(iterations):
        # compute effect of next move on page ranks
        new_rank = [0] * pages
        for row in range(pages):
            for col in range(pages):
                new_rank[row] += rank[col] * trans_matrix[col][row]

        for page in range(pages):
            rank[page] = new_rank[page]

    for page in range(pages):
        print '{:8.5f}'.format(rank[page]),
    print


if __name__ == '__main__':
    main()
